from .stack import Stack


class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None


class BTree:
    def __init__(self, l=()):
        assert isinstance(l, (list, tuple))
        self.root = None
        self.count = 0
        self.stack = Stack(100)

        if l:
            self.root = self.build(l, 0, len(l) - 1)

    def build(self, l, min, max):
        self.count += 1
        middle = int((min + max) / 2)
        node = Node()
        node.data = l[middle]

        if middle > min:
            node.left = self.build(l, min, middle - 1)
            # print("Create left node: %d" % (node.left.data))

        if middle < max:
            node.right = self.build(l, middle + 1, max)
            # print("Create right node: %d" % (node.right.data))

        print("* Create node: %d" % node.data)
        return node

    def __len__(self):
        return self.count

    def _foreach(self, node, func):
        if node is None:
            return

        func(node.data)

        if node.left:
            self._foreach(node.left, func)
        if node.right:
            self._foreach(node.right, func)

    def find(self, node, data, stack=None):
        if stack is not None:
            stack.push(node)

        if node.data == data:
            return data
        else:
            # 通过左节点找数据
            if node.left:
                d = self.find(node.left, data, stack)
                if d:
                    return d
            # 通过右节点找数据
            if node.right:
                d = self.find(node.right, data, stack)
                if d:
                    return d

            if stack is not None:
                stack.pop()

            return None

    def find2(self, node, data):
        print(node.data)
        if node.data == data:
            return data
        else:
            if node.left:
                if data < node.data:
                    d = self.find2(node.left, data)
                    if d:
                        return d
            if node.right:
                if data > node.data:
                    d = self.find2(node.right, data)
                    if d:
                        return d
        return None

    def insert(self, root, data):
        if data == root.data:
            return "cunzai"
        else:
            if data > root.data:
                n = root.right
                if n:
                    return self.insert(n, data)
                else:
                    newnode = Node()
                    newnode.data = data
                    root.right = newnode
                    return newnode

            if data < root.data:
                n = root.left
                if n:
                    return self.insert(n, data)
                else:
                    newnode = Node()
                    newnode.data = data
                    root.left = newnode
                    return newnode

    def insert2(self, node, data):
        while True:
            if data < node.data:
                if node.left is None:
                    node.left = Node()
                    node.left.data = data
                    break
                else:
                    node = node.left

            if data > node.data:
                if node.right is None:
                    node.right = Node()
                    node.right.data = data
                    break
                else:
                    node = node.right

        # while node.left:
        #     if node.data > data:
        #         node = node.left
        #
        #     node.left = Node()
        #     node.left.data = data
        #
        # while node.right:
        #     if node.data < data:
        #         node = node.right
        # node.right = Node()
        # node.right.data = data
        #

    def __iter__(self):
        data_list = []

        def func(data):
            data_list.append(data)

        self._foreach(self.root, func)

        return data_list.__iter__()


if __name__ == "__main__":
    l = (2, 3, 4, 5, 6, 7, 8)
    b = BTree(l)
    stack = Stack(100)

    c = b.find2(b.root, 6)
    b.insert(b.root, 9)
    for v in b:
        print(v)

    # if b.find(b.root, 6, stack=stack):
    #     for d in stack:
    #         print(d.data)
    #
    #     stack.clean()
    #
    #     print(len(stack))
    #     print("The data has been found")

    # for x in b:
    #     print(x)
